/**
 * 
 * 输入：root = [1,null,2,3]
 * 输出：[1,2,3]
 * 
 */

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */

var t = {
    val: 3,
    left: {
        val: 1,
        left: null,
        right: null
    },
    right: {
        val: 2,
        left: null,
        right: null
    }
}


//递归实现
var preorderTraversal = function (root) {
    let res = []


    // debugger
    var traversal = (arr, tnode) => {
        // debugger
        arr.push(tnode.val)
        if (tnode.left != null) {
            traversal(arr, tnode.left)
        }
        if (tnode.right != null) {
            traversal(arr, tnode.right)
        }
        //递归终止条件：遍历到树的叶子节点
        return
    }


    if (root) {
        traversal(res, root)
        return res;
    }
    else {
        return res;
    }
}



//迭代实现
var _preorderTraversal = function (root) {
    let stack = []
    let res = []
    if(!root){
        return res
    }
    stack.push(root)
    debugger
    while (stack.length > 0) {
        let node = stack.pop(root)
        res.push(node.val)
        //先将右子树压入栈，因为pop弹出栈顶元素，前序遍历中先访问右子树后访问左子树，因此要将右子树放在栈顶
        if (node.right != null) {
            stack.push(node.right)
        }
        if (node.left != null) {
            stack.push(node.left)
        }
    }
    return res
}

console.log(_preorderTraversal(t))